#include <stdlib.h>
#include "bstree.h"

ptnode nil;

ptnode newtree()
{
  ptnode head;			/* head node */

  nil = (ptnode)malloc(sizeof(*nil));
  nil->key = -1;
  nil->left = nil;
  nil->right = nil;
  nil->p = nil;
  nil->color = 'B';
  head = (ptnode)malloc(sizeof(*head));
  head->left = head->right = nil; /* both left and right will point to root[t],
				   so we can use either to locate root[t]*/

  return head;
}

ptnode newtnode(long v)
{
  ptnode z = (ptnode)malloc(sizeof(*z));
  z->key = v;
  z->left = nil;
  z->right = nil;
  z->p = nil;

  return z;
}

ptnode tree_minimum(ptnode x)
{
  while (x->left != nil)
    x = x->left;
  return x;
}

ptnode treeroot(ptnode t)
{
  return t->left;		/* t->right is also ok */
}

void newtreeroot(ptnode t, ptnode x)
{
  t->left = t->right = x;
  x->p = nil;
}

ptnode tree_successor(ptnode x)
{
  ptnode y;

  if (x->right != nil)
    return tree_minimum(x->right);
  y = x->p;
  while (y != nil && x == y->right) {
    x = y;
    y = y->p;
  }
  return y;
}

void tree_insert(ptnode t, ptnode z)
{
  ptnode x, y;

  x = treeroot(t);
  y = nil;
  while (x != nil) {
    y = x;
    if (z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  z->p = y;
  if (y == nil)
    newtreeroot(t, z);
  else if (z->key < y->key)
    y->left = z;
  else
    y->right = z;
}

ptnode tree_search(ptnode x, long k)
{
  if (x == nil || x->key == k)
    return x;
  if (k < x->key)
    return tree_search(x->left, k);
  else
    return tree_search(x->right, k);
}

ptnode tree_delete(ptnode t, ptnode z)
{
  ptnode x, y;

  if (z->left == nil || z->right == nil)
    y = z;
  else
    y = tree_successor(z);
  if (y->left != nil)
    x = y->left;
  else
    x = y->right;
  if (x != nil)
    x->p = y->p;
  if (y->p == nil)		/* y is root */
    newtreeroot(t, x);
  else if (y == y->p->left)
    x = y->p->left;
  else
    x = y->p->right;
  if (y != z)
    z->key = y->key;
  return y;
}
